package 原地置换法;

import java.math.BigInteger;

/**
 * 1. 问题描述
 *      给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,最终把它置换成a1,b1,a2,b2,...an,bn。
 *
 * 2. 算法分析
 *      通过观察可知bk向后移动n个单位就是置换之后的位置，
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q1_完美洗牌问题 {
    public static void main(String[] args) {
        byte[] a = {1,1,1,1,1};
        BigInteger bigInteger = new BigInteger(a);
        System.out.println(bigInteger.mod(new BigInteger("4")));

    }

    /**
     * 找元素的放置规律
     * temp[2 * i] = cards[i];
     * temp[2 * (i-cards.length/2) + 1] = cards[i];
     * 时间复杂度为O(n) 空间复杂度也为O(n)
     * @param cards
     */
    public static void shuffle1(int[] cards) {
        int[] temp = new int[cards.length];
        for(int i = 0; i < cards.length; i++) {
            if (i < cards.length / 2) { // a元素
                temp[2 * i] = cards[i];
            } else { // b元素
                // i = n 将cards[i] 置换到 temp[1];
                // i = n + 1 将cards[i] 置换到 temp[3];
                // i = n + 2 将cards[i] 置换到 temp[5];
                temp[2 * (i-cards.length/2) + 1] = cards[i];
            }
        }
        for (int i = 0; i < temp.length; i++) {
            cards[i] = temp[i];
        }
    }

    /**
     * 第二种方式 通过模运算，可以省略下面的判断句，简化代码，但是时间和空间和上述大致相同
     * 分析：
     *     假设当前牌组顺序为{1,2,3,...,n,n+1,n+2,...2*n},洗牌之后的顺序{1,n+1,2,n+2,3,n+3,4,n+4,...,n,2*n}
     *     将上述的牌组转化为在数组中的索引{0,1,2,3,...,n-1,n,n+1,n+2,...,2*n-1},洗牌之后的索引顺序改变为如下：
     *          {0,n,1,n+1,2,n+2,...,n-1,2*n-1}
     *  统一下面的规律：
     *      temp[2 * i] = cards[i];
     *      temp[2 * (i-cards.length/2) + 1] = cards[i];
     *
     *      2 * i ---> i
     *      2 * i - len + 1 ---> i
     *
     * @param cards
     */
    public static void shuffle2(int[] cards) {
        int[] temp = new int[cards.length];

    }



}
